BZOJ2326【HNOI2011】数学作业 <矩阵快速幂优化DP>

Problem

【HNOI2011】数学作业

Description

数学成绩优异，于是老师给留了一道非常难的数学作业题：
给定正整数和，要求计算的值，其中是将所有正整数顺序连接起来得到的数。
例如，。
想了大半天终于意识到这是一道不可能手算出来的题目，于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。

Input

只有一行且为用空格隔开的两个正整数和。

Output

仅包含一个非负整数，表示的值。

Sample Input

13 13

Sample Output

HINT

且。

标签：DP 矩阵快速幂

Solution

显然是矩阵快速幂优化。

设顺次连接后模的值为，所求为。
构建矩阵。由于每次都是将乘后加上，需要三个参数，即,,。构造的转移矩阵：

分成若干的区间做矩阵快速幂后乘起来即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
lnt n, m, f;
struct Matrix {
    lnt ele[3][3];
    Matrix () {memset(ele, 0, sizeof ele);}
    inline Matrix operator * (const Matrix &x) const {
        Matrix ret;
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) for (int k = 0; k < 3; k++)
            ret.ele[i][j] = (ret.ele[i][j]+ele[i][k]*x.ele[k][j]%m)%m;
        return ret;
    }
};
Matrix Power(Matrix a, lnt k) {
    Matrix ret;
    for (int i = 0; i < 3; i++)
        ret.ele[i][i] = 1;
    for (; k; k >>= 1, a = a*a)
        if (k&1) ret = ret*a;
    return ret;
}
int main() {
    read(n), read(m);
    for (lnt i = 1; i <= n; i *= 10) {
        Matrix a, b;
        a.ele[0][0] = f, a.ele[0][1] = (i-1)%m, a.ele[0][2] = 1;
        b.ele[0][0] = i*10%m, b.ele[0][1] = 0, b.ele[0][2] = 0;
        b.ele[1][0] = 1, b.ele[1][1] = 1, b.ele[1][2] = 0;
        b.ele[2][0] = 1, b.ele[2][1] = 1, b.ele[2][2] = 1;
        a = a*Power(b, min(n, i*10-1)-i+1), f = a.ele[0][0];
    }
    return printf("%lld\n", f), 0;
}